import java.util.Arrays;

public class LeetCode1818 {

    public static void main(String[] args) {
        int[] nums1 = {1, 10, 4, 4, 2, 7};
        int[] nums2 = {9, 3, 5, 1, 7, 4};

        System.out.println(minAbsoluteSumDiff(nums1, nums2));
    }

    public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        long sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            // 两个数相同跳过对比
            if (nums1[i] == nums2[i]) {
                continue;
            }
            // 算出差值
            int diff = Math.abs(nums1[i] - nums2[i]);
            // 算总差值
            sum += diff;

            // 开始二分查找 最接近的数值
            int left = 0, right = n - 1;
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (sorted[mid] <= nums2[i]) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            // 计算最近数的差值
            int newDiff = Math.abs(sorted[right] - nums2[i]);
            // 最大的数还小于 target
            if (right + 1 < n) {
                newDiff = Math.min(newDiff, sorted[right + 1] - nums2[i]);
            }
            // 差值
            if (newDiff < diff) {
                max = Math.max(max, diff - newDiff);
            }
        }
        return (int) ((sum - max) % MOD);
    }

}
